/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/submissions/561805460/
 * 300. 最长递增子序列
 * medium 陈贝纯 2024.09.05
 * 经典线性
 */

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int>dp(n,1);
        int m=1;
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;--j){
                if(nums[j]<nums[i]&&dp[i]<dp[j]+1)
                dp[i]=dp[j]+1;
            }
            m=max(m,dp[i]);
        }
        return m;
    }
};